package cn.xaut.杂货;

/**
 * 84. 柱状图中最大的矩形
 */
public class demo84 {

    // 1.暴力解法
    public int largestRectangleArea(int[] heights) {

        int res = 0;
        for (int i = 0; i < heights.length; i++) {
            int height = heights[i];
            int width = 1;
            for (int j = i + 1; j < heights.length; j++) {
                if (heights[j] < height) 
                    break;
                width ++;
            }
            for (int j = i - 1; j >= 0 ; j--) {
                if (heights[j] < height)
                    break;
                width ++;
            }
            int area = width * height;
            res = Math.max(res, area);
        }
        
        return res;
    }

    public static void main(String[] args) {

        int[] heights = {2, 1, 5, 6, 2, 3};
        System.out.println(new demo84().largestRectangleArea(heights));
    }
}
